/*
如何手写一个堆
1.插入一个数             heap[ ++ size] = x; up(size)
2.求集合中的最小值        heap[1];堆顶元素
3.删除最小值             heap[1] = heap[size]; size--;down(1) 用最后一个覆盖第一个，删除最后一个，然后做down
4.删除任意一个元素        heap[k] = heap[size]; size--; down(k); up(k);
5.修改任意一个元素        heap[k] = x; size--; down(k); up(k); 变大往下，变小往上
*/
/*
基本原理：优先级队列差不多，用一维数组去存数据
父节点下标：x
左儿子下标：2x
右儿子下标：2x+1
【注】根节点下标从1开始
*/

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

const int N = 100010;
int n, m;
int head[N],ph[N], hp[N], size;

//带映射关系
void head_swap(int a, int b){
    swap(head[a], head[b]);
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
}

void down(int u){
    int t = u;
    if(2 * u < size && head[2*u] < head[t]) t = 2*u;
    if(2 * u + 1< size && head[2*u + 1] < head[t]) t = 2*u + 1;
    //if(head[2*u + 1] < head[2*u]) swap(head[2*u + 1], head[2*u]);
    if(t != u){
        head_swap(t, u);
        down(t);
    }
}

void up(int u){
    while(u / 2 && head[u/2] > head[u]){
        head_swap(u/2, u);
        u /= 2;
    }
}



int main(){
    scanf("%d", &n);
    while(n--){
        char op[10];
        scanf("%s", op);
        int k , x;
        //I 插入一个数
        if(!strcmp(op, "I")){
            scanf("%d", &x);
            size++;
            m ++;
            ph[m] = size, hp[size] = m;
            head[size] = x;
            up(size);
        }
        //PM 输出当前最小值
        else if(!strcmp(op, "PM")) printf("%d\n", head[1]);
        //DM 删除当前集合的最小值（同时有多个，那就删除最早的那个）
        else if(!strcmp(op, "DM")){
            head_swap(1, size);
            size --;
            down(1);
        }
        //D 删除第K个插入的数
        else if(!strcmp(op, "D")){
            scanf("%d", &k);
            k = ph[k];
            head_swap(k, size);
            size--;
            down(k), up(k);
        } 
        else {
            scanf("%d%d", &k, &x);
            head[ph[k]] = x;
            down(k), up(k);
        }

    }
    
    
    
    return 0;
}
